package com.algorithm.dp;

/**
 * 硬币问题:有1/2/5面值的硬币若干,试问组成金额为X的最少银币组合是?
 * 类似完全背包的解法
 */
public class Coin {
    public static void main(String[] args) {
        Integer[] coinArr = {1,3,5,7};
        int target = 30;
        calcMinCoins00(coinArr, target);
        calcMinCoins01(coinArr, target);
    }

    /**
     * 使用双数组计算最小硬币数,类似01背包. dp[i][j] = min{dp[i-1][j],dp[i][j-v[j]]+1}
     * @param coinArr
     * @param target
     */
    public static void calcMinCoins00(Integer[] coinArr, int target) {
        Integer[][] dp = new Integer[coinArr.length +1][target +1];
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                try {
                    int use = dp[i][j - coinArr[i - 1]] + 1;
                    dp[i][j] = Math.min(use,dp[i-1][j]);
                }catch (Exception e){
                    dp[i][j] = dp[i-1][j];
                }

            }
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println(dp[dp.length-1][dp[0].length-1]);
    }

    /**
     * 考虑到双数组中和01背包类似.可以优化为单数组结构 dp[i] = min{dp[i],dp[i-v[i]]+1}
     * @param coinArr
     * @param target
     */
    public static final void calcMinCoins01(Integer[] coinArr, int target) {
        int[] dp = new int[target + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = i;
        }

        for (int i = 0; i < coinArr.length; i++) {
            for (int j = 1; j < dp.length; j++) {

                if (j > coinArr[i]){
                    dp[j] = Math.min(dp[j],dp[j-coinArr[i]]+1);
                }
            }
        }
        System.out.println(dp[dp.length-1]);
    }

}
